/***************************************************
 * @Author: OBKoro1
 * @Create: 2020-03-29
 * @LastEditors: OBKoro1
 * @LastEditTime: 2020-03-29
 * @FilePath: \leetcode-exercise\5-最长回文子串\5.c
 ****************************************************/
#define MAX_SIZE 1001
static int DP[MAX_SIZE][MAX_SIZE] = {0};
static char res[MAX_SIZE];
char *longestPalindrome(char *s)
{
    int i;
    int j;
    int st = 0;
    int maxlen = 1;
    int L = strlen(s);
    // 默认初始化为0
    memset(DP, 0, sizeof(DP));
    for (i = 0; i < L; i++)
    {
        DP[i][i] = 1;
    }
    // 一般的DP 转移方程
    for (j = 1; j < L; j++)
    {
        for (i = 0; i < j; i++)
        {
            if (s[i] == s[j])
            {
                if ((j - i) < 3)
                {
                    DP[i][j] = 1;
                }
                else
                {
                    DP[i][j] = DP[i + 1][j - 1];
                }
            }
            //记住最大的回文子串的起始位置
            if ((DP[i][j] == 1) && (j - i + 1) > maxlen)
            {
                st = i;
                maxlen = j - i + 1;
            }
        }
    }
    // 根据st和 maxlen 取出回文串的字符
    for (i = 0; i < maxlen; i++)
    {
        res[i] = s[st + i];
    }
    res[maxlen] = '\0';
    return res;
}